Importing packages and setting the directories

library(lubridate)
library(data.table) #convert seconds to days
library(plotly) #interactive plots
library(moments) #to get skewness
library(factoextra) #to visualize clusters
library(plyr)
library(svMisc)

getwd()
[1] "C:/Users/pares/OneDrive/Documents/assessments/online retail"
setwd("C:/Users/pares/OneDrive/Documents/assessments/online retail")

Importing data

data <- read.csv("OnlineRetail.csv",stringsAsFactors = FALSE)
str(data)
'data.frame':   541909 obs. of  8 variables:
 $ InvoiceNo  : chr  "536365" "536365" "536365" "536365" ...
 $ StockCode  : chr  "85123A" "71053" "84406B" "84029G" ...
 $ Description: chr  "WHITE HANGING HEART T-LIGHT HOLDER" "WHITE METAL LANTERN" "CREAM CUPID HEARTS COAT HANGER" "KNITTED UNION FLAG HOT WATER BOTTLE" ...
 $ Quantity   : int  6 6 8 6 6 2 6 6 6 32 ...
 $ InvoiceDate: chr  "12/1/2010 8:26" "12/1/2010 8:26" "12/1/2010 8:26" "12/1/2010 8:26" ...
 $ UnitPrice  : num  2.55 3.39 2.75 3.39 3.39 7.65 4.25 1.85 1.85 1.69 ...
 $ CustomerID : int  17850 17850 17850 17850 17850 17850 17850 17850 17850 13047 ...
 $ Country    : chr  "United Kingdom" "United Kingdom" "United Kingdom" "United Kingdom" ...

We have 541,909 rows. Here, every row belongs to a separate product bought per invoice. This means, if customer bought 3 items in a single invoice, the data will have 3 separate rows for the particular invoice.

We need to correct data types for invoice-date. InvoiceNo is a string (It includes cancelled invoices starting with “C”)

#Converting invoice date to date type
data$InvoiceDate <- strptime(data$InvoiceDate, format = "%m/%d/%Y %H:%M")
summary(data)
  InvoiceNo          StockCode         Description           Quantity          InvoiceDate                 
 Length:541909      Length:541909      Length:541909      Min.   :-80995.00   Min.   :2010-12-01 08:26:00  
 Class :character   Class :character   Class :character   1st Qu.:     1.00   1st Qu.:2011-03-28 11:34:00  
 Mode  :character   Mode  :character   Mode  :character   Median :     3.00   Median :2011-07-19 17:17:00  
                                                          Mean   :     9.55   Mean   :2011-07-04 13:59:07  
                                                          3rd Qu.:    10.00   3rd Qu.:2011-10-19 11:27:00  
                                                          Max.   : 80995.00   Max.   :2011-12-09 12:50:00  
                                                                                                           
   UnitPrice           CustomerID       Country         
 Min.   :-11062.06   Min.   :12346    Length:541909     
 1st Qu.:     1.25   1st Qu.:13953    Class :character  
 Median :     2.08   Median :15152    Mode  :character  
 Mean   :     4.61   Mean   :15288                      
 3rd Qu.:     4.13   3rd Qu.:16791                      
 Max.   : 38970.00   Max.   :18287                      
                     NA's   :135080                     

Observations about the data…

  1. A lot of customer IDs are missing – as we cant segment non existing customers – we can remove them from dataset
  2. There are negative values in quantity!
  3. We have negative unit price for few products. Something is wrong here.
  4. The data is from a time range of 1st December, 2010 to 9th December,2011. A little above one year.

Before removing non-existent customers, lets look at negative values in quantity and unit-price.

sum(data$Quantity < 0) 
[1] 10624

8,905 entries have negative values of quantity

head(data[data$Quantity < 0,]) 

Oh. This could be the cancelled items (InvoiceNo starting with “C”)! — When the customer is returning the item, quantity is subtracted.

We need a column to separate cancelled invoices from purchases.

#Creating a column that separates the purchased items vs the returned items!
data$purchased_item <- ifelse(grepl("C",data$InvoiceNo, fixed = TRUE) == TRUE, 0,1) 

Is this the case with unit price too?

subset(data,data$UnitPrice < 0)

Bad debt is adjusted. These transactions were made by the operator to adjust money issues. Since, there is no customer involved here, eliminating this would not do any harm to us.

#Removing non-existent customer IDs
data <- na.omit(data) 

How many customers are there in total?

length(unique(data$CustomerID))
[1] 4372

And, how many cancelled invoices do we have?

length(unique(data$InvoiceNo))
[1] 22190

4,300 odd customers have made approx. 19,000 purchases in the given year.

Lets, look at our only categorical variable - country.

sort(table(data$Country)) 

        Saudi Arabia              Bahrain       Czech Republic               Brazil            Lithuania 
                  10                   17                   30                   32                   35 
             Lebanon                  RSA   European Community United Arab Emirates                Malta 
                  45                   58                   61                   68                  127 
              Greece               Canada              Iceland            Singapore          Unspecified 
                 146                  151                  182                  229                  244 
              Israel                  USA               Poland                Japan              Denmark 
                 250                  291                  341                  358                  389 
             Austria               Sweden               Cyprus              Finland      Channel Islands 
                 401                  462                  622                  695                  758 
               Italy               Norway            Australia             Portugal          Switzerland 
                 803                 1086                 1259                 1480                 1877 
             Belgium          Netherlands                Spain                 EIRE               France 
                2069                 2371                 2533                 7485                 8491 
             Germany       United Kingdom 
                9495               361878 

Our customers come from a variety of countries. UK having the most transactions. There are researches done that show, purchasing behaviour and customers vary from different geographical locations. It would be wise, to consider similar customers and group them accordingly.

Lets limit the data and consider only transactions coming from UK.

data <- subset(data,data$Country == "United Kingdom")

How many customers are we dealing with now?

cat("We have",length(unique(data$CustomerID)),"customers and a total of",length(unique(data$InvoiceNo)),"different invoices")
We have 3950 customers and a total of 19857 different invoices

We can now create our RFM metrics, but we need to consider cancelled orders to calculate recency and frequency variables.

#———————–LETS RFM————————-

#Calculate 3 different scores for each customer #1. RECENCY – How recently has the customer made his/her purchase? #2. FREQUENCY – How frequent is the customer? How many purchases over the given time frame? #3. MONETARY VALUE – How much amount does each customer bring in?

#Creating a new dataframe 
customers <- as.data.frame(unique(data$CustomerID))
colnames(customers) <- "CustomerID"

#————RECENCY——————–

data$recency <- (max(data$InvoiceDate) + days(1)) - data$InvoiceDate 
data$recency <- as.numeric(data$recency)
#Now this is in seconds, lets convert it in number of days...
#data$recency <- seconds_to_period(data$recency)
#data$recency <- data$recency@day + data$recency@hour/24 + data$recency@minute/(24*60) + data$recency@.Data/(24*60*60)

#Considering only the purchases made
temp <- subset(data, data$purchased_item == 1)

recency <- aggregate(recency ~ CustomerID, data = temp, FUN = min, na.rm = TRUE)

customers <- merge(customers, recency, all = TRUE)

remove(recency)

#————FREQUENCY——————


freq <- aggregate(InvoiceNo ~ CustomerID, data = temp, FUN = uniqueN)
customers <- merge(customers,freq, all = TRUE, by = "CustomerID")
colnames(customers)[3]  <- "Frequency"

remove(freq)

#———-MONETARY VALUE—————



data$revenue <- data$Quantity * data$UnitPrice

revenue <- aggregate(revenue ~ CustomerID, data = data, FUN = sum)
customers <- merge(customers,revenue, all = TRUE)
remove(revenue)

summary(customers)
   CustomerID       recency         Frequency          revenue        
 Min.   :12346   Min.   :  1.00   Min.   :  1.000   Min.   : -4287.6  
 1st Qu.:14208   1st Qu.: 18.06   1st Qu.:  1.000   1st Qu.:   282.2  
 Median :15572   Median : 51.08   Median :  2.000   Median :   627.1  
 Mean   :15562   Mean   : 92.73   Mean   :  4.246   Mean   :  1713.4  
 3rd Qu.:16914   3rd Qu.:143.09   3rd Qu.:  5.000   3rd Qu.:  1521.8  
 Max.   :18287   Max.   :374.12   Max.   :210.000   Max.   :256438.5  
                 NA's   :29       NA's   :29                          

We have 29 customers where we have NA values. These are the customers who have cancelled orders in our original data, but their purchased orders are not present. Therefore, we will not not consider these customers and remove them.

customers <- na.omit(customers)
summary(customers)
   CustomerID       recency         Frequency          revenue        
 Min.   :12346   Min.   :  1.00   Min.   :  1.000   Min.   : -1165.3  
 1st Qu.:14208   1st Qu.: 18.06   1st Qu.:  1.000   1st Qu.:   289.8  
 Median :15569   Median : 51.08   Median :  2.000   Median :   633.7  
 Mean   :15561   Mean   : 92.73   Mean   :  4.246   Mean   :  1728.4  
 3rd Qu.:16913   3rd Qu.:143.09   3rd Qu.:  5.000   3rd Qu.:  1530.8  
 Max.   :18287   Max.   :374.12   Max.   :210.000   Max.   :256438.5  

#Observations…

There are negative values of revenue – probably customers who purchased something before the time frame given, but returned it in the given timeframe! Setting these values to zero!

customers$revenue[customers$revenue < 0] <- 0

This looks much better now.

sum(customers$recency == 0)
[1] 0

#—————-PRE-PROCESSING DATA ———————

Lets look at outliers now.

Before, evaluating outliers, lets do a pareto analysis to understand how outliers can be a crucial factor here.

#———–The 80/20 rule / Pareto Analysis————

– Pareto Analysis – The rule says that more or less, 80% of the results come from the 20% of the causes! In this context, around 80% of sales should be caused by 20% of the customers. Meaning, top 20% customers contribute most to the sales – these would be are our high value customers! Lets see if this is true here.


pareto_cutoff <- 0.8*sum(customers$revenue)

customers <- customers[order(customers$revenue, decreasing = TRUE),]

customers$pareto <- ifelse(cumsum(customers$revenue) <= pareto_cutoff,"Top 20%","Bottom 80%") 
customers$pareto <- as.factor(customers$pareto)

round(prop.table(table(customers$pareto)),2) 

Bottom 80%    Top 20% 
      0.71       0.29 

This is close to 70/30 rule, but close enough! So, we have around 29% customers contributing to 71% of the sales (revenue)

customers <- customers[order(customers$revenue),]

# Lets look at it visually!

p1 <- ggplot(data = customers) +
  geom_point(aes(x = Frequency,y = revenue, color = recency, shape = pareto)) + ggtitle("Original Values") + scale_shape_manual(name = "80/20 rule",values = c(3,8)) + theme(legend.position = "top")

ggplotly(p1)

NA

This map is very hard to read. Almost all the bottom 80% of customers are grouped together in lower corner. We need to evaluate RFM variables for skewness and deal accordingly.

#——How skewed is out data?———

  
ggplot(data = customers, aes(x = recency)) +
  geom_histogram()


ggplot(data = customers, aes(x = Frequency)) +
  geom_histogram()


ggplot(data = customers, aes(x = revenue)) +
  geom_histogram()

NA
NA
NA

Lets, also look at mathematically

skewness(customers$recency)
[1] 1.244409
skewness(customers$Frequency)
[1] 10.80211
skewness(customers$revenue)
[1] 23.27612

All the variables are positively skewed! Lets take log tranform of each! And, We need to tranform the data (scale and normalize it!)

customers$log_recency <- log(customers$recency)
customers$log_frequency <- log(customers$Frequency)

customers$revenue <- customers$revenue + 0.01 #Since, there are 0 values, we dont wanna take log(0)
customers$log_revenue <- log(customers$revenue)

#Lets scale the data using Z- scores!

customers$z_recency <-  scale(customers$log_recency, scale = TRUE, center = TRUE)
customers$z_frequency <-  scale(customers$log_frequency, scale = TRUE, center = TRUE)
customers$z_revenue <- scale(customers$log_revenue, scale = TRUE, center = TRUE)

Lets look at the result now!

#Visualizing the log transformed and scaled variables!

p2 <- ggplot(data = customers) +
  geom_point(aes(x = log_frequency,y = log_revenue, color = log_recency, shape = pareto)) + ggtitle("Log Tranformed values") + scale_shape_manual(name = "80/20 rule",values = c(1,2))

ggplotly(p2)

NA

This is better to read. We now can see how top 20% are higher in log_frequency, log_revenue and log_recency.

#Top Right Corner – has quite a few outliers – these are our high frequency; high revenue; and fairly recent customers – #Bottom Left Corner – these are outliers too – with low frequency; revenue

Lets see the results for scaled variables too.

p3 <- ggplot(data = customers) +
  geom_point(aes(x = z_frequency,y = z_revenue, color = z_recency, shape = pareto)) + ggtitle("Scaled Values") + scale_shape_manual(name = "80/20 rule",values = c(1,2))

ggplotly(p3)

NA
NA

Both of these plots are almost similar- but now we can better analyze the data – Outliers are better visible!

The individual points includes multiple customers. Lets see, how many customers are there in the lowest point?

unique(customers$CustomerID[customers$log_revenue < 0] )
 [1] 12346 13256 13364 13672 13762 14437 14557 14792 15802 15823 16454 16546 16742 16878 17548 17603 18072 18268
[19] 18274

Around 19 customers who bring very little value to the business!

#————————–MODELLING: K-MEANS ALGORITHM————————

###—- WHY?———-

K-MEANS gives disjoint sets - I wanted each customer to belong to one and only one segment! Also, has a linear time complexity O(n) as opposed to hierarchical which has a quadratic complexity - O(n^2)!

###— Dealing with outliers———-

Although k-means is sensitive to outliers, in our case, these outliers give useful information about our customers. Therefore, we will not remove them from consideration!

#—————-OPTIMAL NUMBER OF CLUSTERS————————–

#k-means requires us to give the number of clusters required! #To get the optimal number of clusters – we can do a number of things — #1. Elbow method #2. Silhouette method #3. Gap - Statistic method

#Goal is to group customers into high value and low value customers!


pre_processed <- customers[,9:11]

fviz_nbclust(pre_processed, kmeans,method = "wss")

#Therefore, the elbow method shows 4 as the optimal number of clusters


fviz_nbclust(pre_processed, kmeans,method = "silhouette")


#The Silhouette method gives 3 as the optimal number of clusters!
#fviz_nbclust(pre_processed, kmeans,method = "gap_stat")

#Gap statistic also gives 3 as the optimal number of clusters!

#Lets try to visualize results for clusters 2 to 10 and compare results!


models <- data.frame(k=integer(),
                     tot.withinss=numeric(),
                     betweenss=numeric(),
                     totss=numeric(),
                     rsquared=numeric())


for (k in 1:10){
  
  output <- kmeans(pre_processed, centers = k,nstart = 20)
  
  variable_name <- paste("Cluster",k,sep = "_")
  
  customers[,(variable_name)] <- output$cluster
  
  customers[,(variable_name)] <- factor(customers[,(variable_name)], levels = c(1:k))
  
  
  
  #Graphing the clusters
  colors <- c('red','orange','green3','deepskyblue','blue','darkorchid4','violet','pink1','tan3','black')
  title <- paste("Cluster analysis with",k,"Clusters")
  
  p4 <- ggplot(data = customers,aes(x = log_frequency, y = log_revenue)) +
    geom_point(aes(color = customers[,(variable_name)])) + labs(color = "Cluster group") + ggtitle(title)
  
  print(ggplotly(p4))
  
  #Cluster centres in original metrics
  
  cluster_centres <- ddply(customers,.(customers[,(variable_name)]), summarize,
                           revenue = round(median(revenue),2),
                           recency = round(median(recency),2),
                           frequency = round(median(Frequency),2)
  )
  
  names(cluster_centres)[names(cluster_centres) == "customers[, (variable_name)]"] <- "Clusters"
  
  print(cluster_centres)
  cat("\n")
  cat("\n")
  #Model Information
  
  models[k,"k"] <- k
  models[k,"tot.withinss"] <- output$tot.withinss
  models[k,"betweenss"] <- output$betweenss
  models[k,"totss"] <- output$totss
  models[k,"rsquared"] <- output$betweenss/output$totss
  
}

NANA

NANA

NANA

NANA

NANA

NANA

NANA

did not converge in 10 iterations

NANA

NANA

Final Solution

scatter3d(x = customers$log_revenue, y = customers$log_frequency, z = customers$log_recency,
          groups = customers$Cluster_4,
          xlab = "Frequency (Log-transformed)",
          ylab = "Monetary Value (log-transformed)",
          zlab = "Recency (Log-transformed)",
          surface.col = colors,
          axis.scales = FALSE,
          surface = FALSE, # produces the horizonal planes through the graph at each level of monetary value
          fit = "smooth",
          ellipsoid = TRUE, # to graph ellipses uses this command and comment out "surface = TRUE"
          grid = FALSE,
          axis.col = c("black", "black", "black"))

#———–Final Analysis——————

#As the number of clusters increase, there interpretability is also affected.

#Cluster analysis with 2 clusters seems overly simplified!

#Cluster analysis with 3 clusters basically gives cluster 3 as high value customers, cluster 1 and 2 are similar (low value!)

#The decision should be based upon how the business plans to use the results, and the level of granularity they want to see in the clusters. I’d suggest 4 number of clusters should be good — Cluster 4 – high value customers; Cluster 1 and Cluster 2 – mid value customers and Cluster 3 are the zero value customers with low frequency and low revenue and are not very recent.

LS0tDQp0aXRsZTogIlIgTm90ZWJvb2siDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQpJbXBvcnRpbmcgcGFja2FnZXMgYW5kIHNldHRpbmcgdGhlIGRpcmVjdG9yaWVzDQoNCmBgYHtyfQ0KbGlicmFyeShsdWJyaWRhdGUpDQpsaWJyYXJ5KGRhdGEudGFibGUpICNjb252ZXJ0IHNlY29uZHMgdG8gZGF5cw0KbGlicmFyeShwbG90bHkpICNpbnRlcmFjdGl2ZSBwbG90cw0KbGlicmFyeShtb21lbnRzKSAjdG8gZ2V0IHNrZXduZXNzDQpsaWJyYXJ5KGZhY3RvZXh0cmEpICN0byB2aXN1YWxpemUgY2x1c3RlcnMNCmxpYnJhcnkocGx5cikNCmxpYnJhcnkoc3ZNaXNjKQ0KDQpnZXR3ZCgpDQpzZXR3ZCgiQzovVXNlcnMvcGFyZXMvT25lRHJpdmUvRG9jdW1lbnRzL2Fzc2Vzc21lbnRzL29ubGluZSByZXRhaWwiKQ0KDQpgYGANCg0KSW1wb3J0aW5nIGRhdGENCg0KYGBge3J9DQpkYXRhIDwtIHJlYWQuY3N2KCJPbmxpbmVSZXRhaWwuY3N2IixzdHJpbmdzQXNGYWN0b3JzID0gRkFMU0UpDQpzdHIoZGF0YSkNCg0KYGBgDQpXZSBoYXZlIDU0MSw5MDkgcm93cy4gSGVyZSwgZXZlcnkgcm93IGJlbG9uZ3MgdG8gYSBzZXBhcmF0ZSBwcm9kdWN0IGJvdWdodCBwZXIgaW52b2ljZS4gVGhpcyBtZWFucywgaWYgY3VzdG9tZXIgYm91Z2h0IDMgaXRlbXMgaW4gYSBzaW5nbGUgaW52b2ljZSwgdGhlIGRhdGEgd2lsbCBoYXZlIDMgc2VwYXJhdGUgcm93cyBmb3IgdGhlIHBhcnRpY3VsYXIgaW52b2ljZS4NCg0KV2UgbmVlZCB0byBjb3JyZWN0IGRhdGEgdHlwZXMgZm9yIGludm9pY2UtZGF0ZS4gSW52b2ljZU5vIGlzIGEgc3RyaW5nIChJdCBpbmNsdWRlcyBjYW5jZWxsZWQgaW52b2ljZXMgc3RhcnRpbmcgd2l0aCAiQyIpDQoNCmBgYHtyfQ0KI0NvbnZlcnRpbmcgaW52b2ljZSBkYXRlIHRvIGRhdGUgdHlwZQ0KZGF0YSRJbnZvaWNlRGF0ZSA8LSBzdHJwdGltZShkYXRhJEludm9pY2VEYXRlLCBmb3JtYXQgPSAiJW0vJWQvJVkgJUg6JU0iKQ0Kc3VtbWFyeShkYXRhKQ0KDQpgYGANCg0KIyBPYnNlcnZhdGlvbnMgYWJvdXQgdGhlIGRhdGEuLi4NCjEuIEEgbG90IG9mIGN1c3RvbWVyIElEcyBhcmUgbWlzc2luZyAtLSBhcyB3ZSBjYW50IHNlZ21lbnQgbm9uIGV4aXN0aW5nIGN1c3RvbWVycyAtLSB3ZSBjYW4gcmVtb3ZlIHRoZW0gZnJvbSBkYXRhc2V0DQoyLiBUaGVyZSBhcmUgbmVnYXRpdmUgdmFsdWVzIGluIHF1YW50aXR5IQ0KMy4gV2UgaGF2ZSBuZWdhdGl2ZSB1bml0IHByaWNlIGZvciBmZXcgcHJvZHVjdHMuIFNvbWV0aGluZyBpcyB3cm9uZyBoZXJlLg0KNC4gVGhlIGRhdGEgaXMgZnJvbSBhIHRpbWUgcmFuZ2Ugb2YgMXN0IERlY2VtYmVyLCAyMDEwIHRvIDl0aCBEZWNlbWJlciwyMDExLiBBIGxpdHRsZSBhYm92ZSBvbmUgeWVhci4NCg0KQmVmb3JlIHJlbW92aW5nIG5vbi1leGlzdGVudCBjdXN0b21lcnMsIGxldHMgbG9vayBhdCBuZWdhdGl2ZSB2YWx1ZXMgaW4gcXVhbnRpdHkgYW5kIHVuaXQtcHJpY2UuDQoNCi0gTmVnYXRpdmUgUXVhbnRpdHkgdmFsdWVzPw0KDQpgYGB7cn0NCnN1bShkYXRhJFF1YW50aXR5IDwgMCkgDQpgYGANCjgsOTA1IGVudHJpZXMgaGF2ZSBuZWdhdGl2ZSB2YWx1ZXMgb2YgcXVhbnRpdHkgDQoNCmBgYHtyfQ0KaGVhZChkYXRhW2RhdGEkUXVhbnRpdHkgPCAwLF0pIA0KYGBgDQpPaC4gVGhpcyBjb3VsZCBiZSB0aGUgY2FuY2VsbGVkIGl0ZW1zIChJbnZvaWNlTm8gc3RhcnRpbmcgd2l0aCAiQyIpISAtLS0gV2hlbiB0aGUgY3VzdG9tZXIgaXMgcmV0dXJuaW5nIHRoZSBpdGVtLCBxdWFudGl0eSBpcyBzdWJ0cmFjdGVkLg0KDQpXZSBuZWVkIGEgY29sdW1uIHRvIHNlcGFyYXRlIGNhbmNlbGxlZCBpbnZvaWNlcyBmcm9tIHB1cmNoYXNlcy4NCg0KYGBge3J9DQojQ3JlYXRpbmcgYSBjb2x1bW4gdGhhdCBzZXBhcmF0ZXMgdGhlIHB1cmNoYXNlZCBpdGVtcyB2cyB0aGUgcmV0dXJuZWQgaXRlbXMhDQpkYXRhJHB1cmNoYXNlZF9pdGVtIDwtIGlmZWxzZShncmVwbCgiQyIsZGF0YSRJbnZvaWNlTm8sIGZpeGVkID0gVFJVRSkgPT0gVFJVRSwgMCwxKSANCmBgYA0KDQpJcyB0aGlzIHRoZSBjYXNlIHdpdGggdW5pdCBwcmljZSB0b28/DQoNCmBgYHtyfQ0Kc3Vic2V0KGRhdGEsZGF0YSRVbml0UHJpY2UgPCAwKQ0KYGBgDQpCYWQgZGVidCBpcyBhZGp1c3RlZC4gVGhlc2UgdHJhbnNhY3Rpb25zIHdlcmUgbWFkZSBieSB0aGUgb3BlcmF0b3IgdG8gYWRqdXN0IG1vbmV5IGlzc3Vlcy4gU2luY2UsIHRoZXJlIGlzIG5vIGN1c3RvbWVyIGludm9sdmVkIGhlcmUsIGVsaW1pbmF0aW5nIHRoaXMgd291bGQgbm90IGRvIGFueSBoYXJtIHRvIHVzLg0KDQpgYGB7cn0NCiNSZW1vdmluZyBub24tZXhpc3RlbnQgY3VzdG9tZXIgSURzDQpkYXRhIDwtIG5hLm9taXQoZGF0YSkgDQpgYGANCg0KSG93IG1hbnkgY3VzdG9tZXJzIGFyZSB0aGVyZSBpbiB0b3RhbD8NCg0KYGBge3J9DQpsZW5ndGgodW5pcXVlKGRhdGEkQ3VzdG9tZXJJRCkpDQpgYGANCg0KQW5kLCBob3cgbWFueSBjYW5jZWxsZWQgaW52b2ljZXMgZG8gd2UgaGF2ZT8NCg0KYGBge3J9DQpsZW5ndGgodW5pcXVlKGRhdGEkSW52b2ljZU5vKSkNCmBgYA0KDQojIDQsMzAwIG9kZCBjdXN0b21lcnMgaGF2ZSBtYWRlIGFwcHJveC4gMTksMDAwIHB1cmNoYXNlcyBpbiB0aGUgZ2l2ZW4geWVhci4NCg0KTGV0cywgbG9vayBhdCBvdXIgb25seSBjYXRlZ29yaWNhbCB2YXJpYWJsZSAtIGNvdW50cnkuDQoNCmBgYHtyfQ0Kc29ydCh0YWJsZShkYXRhJENvdW50cnkpKSANCmBgYA0KDQpPdXIgY3VzdG9tZXJzIGNvbWUgZnJvbSBhIHZhcmlldHkgb2YgY291bnRyaWVzLiBVSyBoYXZpbmcgdGhlIG1vc3QgdHJhbnNhY3Rpb25zLiBUaGVyZSBhcmUgcmVzZWFyY2hlcyBkb25lIHRoYXQgc2hvdywgcHVyY2hhc2luZyBiZWhhdmlvdXIgYW5kIGN1c3RvbWVycyB2YXJ5IGZyb20gZGlmZmVyZW50IGdlb2dyYXBoaWNhbCBsb2NhdGlvbnMuIEl0IHdvdWxkIGJlIHdpc2UsIHRvIGNvbnNpZGVyIHNpbWlsYXIgY3VzdG9tZXJzIGFuZCBncm91cCB0aGVtIGFjY29yZGluZ2x5Lg0KDQojIExldHMgbGltaXQgdGhlIGRhdGEgYW5kIGNvbnNpZGVyIG9ubHkgdHJhbnNhY3Rpb25zIGNvbWluZyBmcm9tIFVLLg0KDQpgYGB7cn0NCmRhdGEgPC0gc3Vic2V0KGRhdGEsZGF0YSRDb3VudHJ5ID09ICJVbml0ZWQgS2luZ2RvbSIpDQpgYGANCg0KSG93IG1hbnkgY3VzdG9tZXJzIGFyZSB3ZSBkZWFsaW5nIHdpdGggbm93Pw0KYGBge3J9DQpjYXQoIldlIGhhdmUiLGxlbmd0aCh1bmlxdWUoZGF0YSRDdXN0b21lcklEKSksImN1c3RvbWVycyBhbmQgYSB0b3RhbCBvZiIsbGVuZ3RoKHVuaXF1ZShkYXRhJEludm9pY2VObykpLCJkaWZmZXJlbnQgaW52b2ljZXMiKQ0KYGBgDQoNCldlIGNhbiBub3cgY3JlYXRlIG91ciBSRk0gbWV0cmljcywgYnV0IHdlIG5lZWQgdG8gY29uc2lkZXIgY2FuY2VsbGVkIG9yZGVycyB0byBjYWxjdWxhdGUgcmVjZW5jeSBhbmQgZnJlcXVlbmN5IHZhcmlhYmxlcy4NCg0KIy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tTEVUUyBSRk0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tDQoNCiNDYWxjdWxhdGUgMyBkaWZmZXJlbnQgc2NvcmVzIGZvciBlYWNoIGN1c3RvbWVyDQojMS4gUkVDRU5DWSAtLSBIb3cgcmVjZW50bHkgaGFzIHRoZSBjdXN0b21lciBtYWRlIGhpcy9oZXIgcHVyY2hhc2U/DQojMi4gRlJFUVVFTkNZIC0tIEhvdyBmcmVxdWVudCBpcyB0aGUgY3VzdG9tZXI/IEhvdyBtYW55IHB1cmNoYXNlcyBvdmVyIHRoZSBnaXZlbiB0aW1lIGZyYW1lPw0KIzMuIE1PTkVUQVJZIFZBTFVFIC0tIEhvdyBtdWNoIGFtb3VudCBkb2VzIGVhY2ggY3VzdG9tZXIgYnJpbmcgaW4/DQoNCmBgYHtyfQ0KI0NyZWF0aW5nIGEgbmV3IGRhdGFmcmFtZSANCmN1c3RvbWVycyA8LSBhcy5kYXRhLmZyYW1lKHVuaXF1ZShkYXRhJEN1c3RvbWVySUQpKQ0KY29sbmFtZXMoY3VzdG9tZXJzKSA8LSAiQ3VzdG9tZXJJRCINCg0KYGBgDQoNCiMtLS0tLS0tLS0tLS1SRUNFTkNZLS0tLS0tLS0tLS0tLS0tLS0tLS0NCg0KYGBge3J9DQpkYXRhJHJlY2VuY3kgPC0gKG1heChkYXRhJEludm9pY2VEYXRlKSArIGRheXMoMSkpIC0gZGF0YSRJbnZvaWNlRGF0ZSANCmRhdGEkcmVjZW5jeSA8LSBhcy5udW1lcmljKGRhdGEkcmVjZW5jeSkNCiNOb3cgdGhpcyBpcyBpbiBzZWNvbmRzLCBsZXRzIGNvbnZlcnQgaXQgaW4gbnVtYmVyIG9mIGRheXMuLi4NCiNkYXRhJHJlY2VuY3kgPC0gc2Vjb25kc190b19wZXJpb2QoZGF0YSRyZWNlbmN5KQ0KI2RhdGEkcmVjZW5jeSA8LSBkYXRhJHJlY2VuY3lAZGF5ICsgZGF0YSRyZWNlbmN5QGhvdXIvMjQgKyBkYXRhJHJlY2VuY3lAbWludXRlLygyNCo2MCkgKyBkYXRhJHJlY2VuY3lALkRhdGEvKDI0KjYwKjYwKQ0KDQojQ29uc2lkZXJpbmcgb25seSB0aGUgcHVyY2hhc2VzIG1hZGUNCnRlbXAgPC0gc3Vic2V0KGRhdGEsIGRhdGEkcHVyY2hhc2VkX2l0ZW0gPT0gMSkNCg0KcmVjZW5jeSA8LSBhZ2dyZWdhdGUocmVjZW5jeSB+IEN1c3RvbWVySUQsIGRhdGEgPSB0ZW1wLCBGVU4gPSBtaW4sIG5hLnJtID0gVFJVRSkNCg0KY3VzdG9tZXJzIDwtIG1lcmdlKGN1c3RvbWVycywgcmVjZW5jeSwgYWxsID0gVFJVRSkNCg0KcmVtb3ZlKHJlY2VuY3kpDQoNCmBgYA0KDQoNCiMtLS0tLS0tLS0tLS1GUkVRVUVOQ1ktLS0tLS0tLS0tLS0tLS0tLS0NCg0KYGBge3J9DQoNCmZyZXEgPC0gYWdncmVnYXRlKEludm9pY2VObyB+IEN1c3RvbWVySUQsIGRhdGEgPSB0ZW1wLCBGVU4gPSB1bmlxdWVOKQ0KY3VzdG9tZXJzIDwtIG1lcmdlKGN1c3RvbWVycyxmcmVxLCBhbGwgPSBUUlVFLCBieSA9ICJDdXN0b21lcklEIikNCmNvbG5hbWVzKGN1c3RvbWVycylbM10gIDwtICJGcmVxdWVuY3kiDQoNCnJlbW92ZShmcmVxKQ0KDQpgYGANCg0KDQojLS0tLS0tLS0tLU1PTkVUQVJZIFZBTFVFLS0tLS0tLS0tLS0tLS0tDQoNCmBgYHtyfQ0KDQoNCmRhdGEkcmV2ZW51ZSA8LSBkYXRhJFF1YW50aXR5ICogZGF0YSRVbml0UHJpY2UNCg0KcmV2ZW51ZSA8LSBhZ2dyZWdhdGUocmV2ZW51ZSB+IEN1c3RvbWVySUQsIGRhdGEgPSBkYXRhLCBGVU4gPSBzdW0pDQpjdXN0b21lcnMgPC0gbWVyZ2UoY3VzdG9tZXJzLHJldmVudWUsIGFsbCA9IFRSVUUpDQpyZW1vdmUocmV2ZW51ZSkNCg0Kc3VtbWFyeShjdXN0b21lcnMpDQpgYGANCg0KV2UgaGF2ZSAyOSBjdXN0b21lcnMgd2hlcmUgd2UgaGF2ZSBOQSB2YWx1ZXMuIFRoZXNlIGFyZSB0aGUgY3VzdG9tZXJzIHdobyBoYXZlIGNhbmNlbGxlZCBvcmRlcnMgaW4gb3VyIG9yaWdpbmFsIGRhdGEsIGJ1dCB0aGVpciBwdXJjaGFzZWQgb3JkZXJzIGFyZSBub3QgcHJlc2VudC4gVGhlcmVmb3JlLCB3ZSB3aWxsIG5vdCBub3QgY29uc2lkZXIgdGhlc2UgY3VzdG9tZXJzIGFuZCByZW1vdmUgdGhlbS4NCg0KDQpgYGB7cn0NCmN1c3RvbWVycyA8LSBuYS5vbWl0KGN1c3RvbWVycykNCnN1bW1hcnkoY3VzdG9tZXJzKQ0KYGBgDQoNCiNPYnNlcnZhdGlvbnMuLi4NCg0KVGhlcmUgYXJlIG5lZ2F0aXZlIHZhbHVlcyBvZiByZXZlbnVlIC0tIHByb2JhYmx5IGN1c3RvbWVycyB3aG8gcHVyY2hhc2VkIHNvbWV0aGluZyBiZWZvcmUgdGhlIHRpbWUgZnJhbWUgZ2l2ZW4sIGJ1dCByZXR1cm5lZCBpdCBpbiB0aGUgZ2l2ZW4gdGltZWZyYW1lISBTZXR0aW5nIHRoZXNlIHZhbHVlcyB0byB6ZXJvIQ0KDQoNCmBgYHtyfQ0KY3VzdG9tZXJzJHJldmVudWVbY3VzdG9tZXJzJHJldmVudWUgPCAwXSA8LSAwDQpgYGANClRoaXMgbG9va3MgbXVjaCBiZXR0ZXIgbm93Lg0KDQpgYGB7cn0NCnN1bShjdXN0b21lcnMkcmVjZW5jeSA9PSAwKQ0KYGBgDQoNCg0KDQojLS0tLS0tLS0tLS0tLS0tLVBSRS1QUk9DRVNTSU5HIERBVEEgLS0tLS0tLS0tLS0tLS0tLS0tLS0tDQoNCiMjIyBMZXRzIGxvb2sgYXQgb3V0bGllcnMgbm93Lg0KDQpCZWZvcmUsIGV2YWx1YXRpbmcgb3V0bGllcnMsIGxldHMgZG8gYSBwYXJldG8gYW5hbHlzaXMgdG8gdW5kZXJzdGFuZCBob3cgb3V0bGllcnMgY2FuIGJlIGEgY3J1Y2lhbCBmYWN0b3IgaGVyZS4NCg0KIy0tLS0tLS0tLS0tVGhlIDgwLzIwIHJ1bGUgLyBQYXJldG8gQW5hbHlzaXMtLS0tLS0tLS0tLS0NCg0KLS0gUGFyZXRvIEFuYWx5c2lzIC0tIFRoZSBydWxlIHNheXMgdGhhdCBtb3JlIG9yIGxlc3MsIDgwJSBvZiB0aGUgcmVzdWx0cyBjb21lIGZyb20gdGhlIDIwJSBvZiB0aGUgY2F1c2VzISBJbiB0aGlzIGNvbnRleHQsIGFyb3VuZCA4MCUgb2Ygc2FsZXMgc2hvdWxkIGJlIGNhdXNlZCBieSAyMCUgb2YgdGhlIGN1c3RvbWVycy4gTWVhbmluZywgdG9wIDIwJSBjdXN0b21lcnMgY29udHJpYnV0ZSBtb3N0IHRvIHRoZSBzYWxlcyAtLSB0aGVzZSB3b3VsZCBiZSBhcmUgb3VyIGhpZ2ggdmFsdWUgY3VzdG9tZXJzISBMZXRzIHNlZSBpZiB0aGlzIGlzIHRydWUgaGVyZS4NCg0KDQpgYGB7cn0NCg0KcGFyZXRvX2N1dG9mZiA8LSAwLjgqc3VtKGN1c3RvbWVycyRyZXZlbnVlKQ0KDQpjdXN0b21lcnMgPC0gY3VzdG9tZXJzW29yZGVyKGN1c3RvbWVycyRyZXZlbnVlLCBkZWNyZWFzaW5nID0gVFJVRSksXQ0KDQpjdXN0b21lcnMkcGFyZXRvIDwtIGlmZWxzZShjdW1zdW0oY3VzdG9tZXJzJHJldmVudWUpIDw9IHBhcmV0b19jdXRvZmYsIlRvcCAyMCUiLCJCb3R0b20gODAlIikgDQpjdXN0b21lcnMkcGFyZXRvIDwtIGFzLmZhY3RvcihjdXN0b21lcnMkcGFyZXRvKQ0KDQpyb3VuZChwcm9wLnRhYmxlKHRhYmxlKGN1c3RvbWVycyRwYXJldG8pKSwyKSANCmBgYA0KVGhpcyBpcyBjbG9zZSB0byA3MC8zMCBydWxlLCBidXQgY2xvc2UgZW5vdWdoISBTbywgd2UgaGF2ZSBhcm91bmQgMjklIGN1c3RvbWVycyBjb250cmlidXRpbmcgdG8gNzElIG9mIHRoZSBzYWxlcyAocmV2ZW51ZSkNCg0KDQpgYGB7cn0NCmN1c3RvbWVycyA8LSBjdXN0b21lcnNbb3JkZXIoY3VzdG9tZXJzJHJldmVudWUpLF0NCg0KIyBMZXRzIGxvb2sgYXQgaXQgdmlzdWFsbHkhDQoNCnAxIDwtIGdncGxvdChkYXRhID0gY3VzdG9tZXJzKSArDQogIGdlb21fcG9pbnQoYWVzKHggPSBGcmVxdWVuY3kseSA9IHJldmVudWUsIGNvbG9yID0gcmVjZW5jeSwgc2hhcGUgPSBwYXJldG8pKSArIGdndGl0bGUoIk9yaWdpbmFsIFZhbHVlcyIpICsgc2NhbGVfc2hhcGVfbWFudWFsKG5hbWUgPSAiODAvMjAgcnVsZSIsdmFsdWVzID0gYygzLDgpKSArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJ0b3AiKQ0KDQpnZ3Bsb3RseShwMSkNCg0KYGBgDQoNClRoaXMgbWFwIGlzIHZlcnkgaGFyZCB0byByZWFkLiBBbG1vc3QgYWxsIHRoZSBib3R0b20gODAlIG9mIGN1c3RvbWVycyBhcmUgZ3JvdXBlZCB0b2dldGhlciBpbiBsb3dlciBjb3JuZXIuIFdlIG5lZWQgdG8gZXZhbHVhdGUgUkZNIHZhcmlhYmxlcyBmb3Igc2tld25lc3MgYW5kIGRlYWwgYWNjb3JkaW5nbHkuDQoNCiMtLS0tLS1Ib3cgc2tld2VkIGlzIG91dCBkYXRhPy0tLS0tLS0tLQ0KDQpgYGB7cn0NCiAgDQpnZ3Bsb3QoZGF0YSA9IGN1c3RvbWVycywgYWVzKHggPSByZWNlbmN5KSkgKw0KICBnZW9tX2hpc3RvZ3JhbSgpDQoNCmdncGxvdChkYXRhID0gY3VzdG9tZXJzLCBhZXMoeCA9IEZyZXF1ZW5jeSkpICsNCiAgZ2VvbV9oaXN0b2dyYW0oKQ0KDQpnZ3Bsb3QoZGF0YSA9IGN1c3RvbWVycywgYWVzKHggPSByZXZlbnVlKSkgKw0KICBnZW9tX2hpc3RvZ3JhbSgpDQoNCg0KDQpgYGANCg0KTGV0cywgYWxzbyBsb29rIGF0IG1hdGhlbWF0aWNhbGx5DQoNCmBgYHtyfQ0Kc2tld25lc3MoY3VzdG9tZXJzJHJlY2VuY3kpDQpza2V3bmVzcyhjdXN0b21lcnMkRnJlcXVlbmN5KQ0Kc2tld25lc3MoY3VzdG9tZXJzJHJldmVudWUpDQoNCmBgYA0KDQpBbGwgdGhlIHZhcmlhYmxlcyBhcmUgcG9zaXRpdmVseSBza2V3ZWQhIExldHMgdGFrZSBsb2cgdHJhbmZvcm0gb2YgZWFjaCEgQW5kLCBXZSBuZWVkIHRvIHRyYW5mb3JtIHRoZSBkYXRhIChzY2FsZSBhbmQgbm9ybWFsaXplIGl0ISkNCg0KDQpgYGB7cn0NCmN1c3RvbWVycyRsb2dfcmVjZW5jeSA8LSBsb2coY3VzdG9tZXJzJHJlY2VuY3kpDQpjdXN0b21lcnMkbG9nX2ZyZXF1ZW5jeSA8LSBsb2coY3VzdG9tZXJzJEZyZXF1ZW5jeSkNCg0KY3VzdG9tZXJzJHJldmVudWUgPC0gY3VzdG9tZXJzJHJldmVudWUgKyAwLjAxICNTaW5jZSwgdGhlcmUgYXJlIDAgdmFsdWVzLCB3ZSBkb250IHdhbm5hIHRha2UgbG9nKDApDQpjdXN0b21lcnMkbG9nX3JldmVudWUgPC0gbG9nKGN1c3RvbWVycyRyZXZlbnVlKQ0KDQojTGV0cyBzY2FsZSB0aGUgZGF0YSB1c2luZyBaLSBzY29yZXMhDQoNCmN1c3RvbWVycyR6X3JlY2VuY3kgPC0gIHNjYWxlKGN1c3RvbWVycyRsb2dfcmVjZW5jeSwgc2NhbGUgPSBUUlVFLCBjZW50ZXIgPSBUUlVFKQ0KY3VzdG9tZXJzJHpfZnJlcXVlbmN5IDwtICBzY2FsZShjdXN0b21lcnMkbG9nX2ZyZXF1ZW5jeSwgc2NhbGUgPSBUUlVFLCBjZW50ZXIgPSBUUlVFKQ0KY3VzdG9tZXJzJHpfcmV2ZW51ZSA8LSBzY2FsZShjdXN0b21lcnMkbG9nX3JldmVudWUsIHNjYWxlID0gVFJVRSwgY2VudGVyID0gVFJVRSkNCg0KYGBgDQoNCkxldHMgbG9vayBhdCB0aGUgcmVzdWx0IG5vdyENCg0KYGBge3J9DQojVmlzdWFsaXppbmcgdGhlIGxvZyB0cmFuc2Zvcm1lZCBhbmQgc2NhbGVkIHZhcmlhYmxlcyENCg0KcDIgPC0gZ2dwbG90KGRhdGEgPSBjdXN0b21lcnMpICsNCiAgZ2VvbV9wb2ludChhZXMoeCA9IGxvZ19mcmVxdWVuY3kseSA9IGxvZ19yZXZlbnVlLCBjb2xvciA9IGxvZ19yZWNlbmN5LCBzaGFwZSA9IHBhcmV0bykpICsgZ2d0aXRsZSgiTG9nIFRyYW5mb3JtZWQgdmFsdWVzIikgKyBzY2FsZV9zaGFwZV9tYW51YWwobmFtZSA9ICI4MC8yMCBydWxlIix2YWx1ZXMgPSBjKDEsMikpDQoNCmdncGxvdGx5KHAyKQ0KDQpgYGANCg0KDQpUaGlzIGlzIGJldHRlciB0byByZWFkLiBXZSBub3cgY2FuIHNlZSBob3cgdG9wIDIwJSBhcmUgaGlnaGVyIGluIGxvZ19mcmVxdWVuY3ksIGxvZ19yZXZlbnVlIGFuZCBsb2dfcmVjZW5jeS4NCg0KI1RvcCBSaWdodCBDb3JuZXIgLS0gaGFzIHF1aXRlIGEgZmV3IG91dGxpZXJzIC0tIHRoZXNlIGFyZSBvdXIgaGlnaCBmcmVxdWVuY3k7IGhpZ2ggcmV2ZW51ZTsgYW5kIGZhaXJseSByZWNlbnQgY3VzdG9tZXJzIC0tDQojQm90dG9tIExlZnQgQ29ybmVyIC0tIHRoZXNlIGFyZSBvdXRsaWVycyB0b28gLS0gd2l0aCBsb3cgZnJlcXVlbmN5OyByZXZlbnVlDQoNCg0KTGV0cyBzZWUgdGhlIHJlc3VsdHMgZm9yIHNjYWxlZCB2YXJpYWJsZXMgdG9vLg0KDQpgYGB7cn0NCnAzIDwtIGdncGxvdChkYXRhID0gY3VzdG9tZXJzKSArDQogIGdlb21fcG9pbnQoYWVzKHggPSB6X2ZyZXF1ZW5jeSx5ID0gel9yZXZlbnVlLCBjb2xvciA9IHpfcmVjZW5jeSwgc2hhcGUgPSBwYXJldG8pKSArIGdndGl0bGUoIlNjYWxlZCBWYWx1ZXMiKSArIHNjYWxlX3NoYXBlX21hbnVhbChuYW1lID0gIjgwLzIwIHJ1bGUiLHZhbHVlcyA9IGMoMSwyKSkNCg0KZ2dwbG90bHkocDMpDQoNCg0KYGBgDQoNCkJvdGggb2YgdGhlc2UgcGxvdHMgYXJlIGFsbW9zdCBzaW1pbGFyLSBidXQgbm93IHdlIGNhbiBiZXR0ZXIgYW5hbHl6ZSB0aGUgZGF0YSAtLSBPdXRsaWVycyBhcmUgYmV0dGVyIHZpc2libGUhDQoNClRoZSBpbmRpdmlkdWFsIHBvaW50cyBpbmNsdWRlcyBtdWx0aXBsZSBjdXN0b21lcnMuIExldHMgc2VlLCBob3cgbWFueSBjdXN0b21lcnMgYXJlIHRoZXJlIGluIHRoZSBsb3dlc3QgcG9pbnQ/DQoNCmBgYHtyfQ0KdW5pcXVlKGN1c3RvbWVycyRDdXN0b21lcklEW2N1c3RvbWVycyRsb2dfcmV2ZW51ZSA8IDBdICkNCmBgYA0KQXJvdW5kIDE5IGN1c3RvbWVycyB3aG8gYnJpbmcgdmVyeSBsaXR0bGUgdmFsdWUgdG8gdGhlIGJ1c2luZXNzIQ0KDQoNCiMtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLU1PREVMTElORzogSy1NRUFOUyBBTEdPUklUSE0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0NCg0KIyMjLS0tLSBXSFk/LS0tLS0tLS0tLQ0KDQpLLU1FQU5TIGdpdmVzIGRpc2pvaW50IHNldHMgLSBJIHdhbnRlZCBlYWNoIGN1c3RvbWVyIHRvIGJlbG9uZyB0byBvbmUgYW5kIG9ubHkgb25lIHNlZ21lbnQhDQpBbHNvLCBoYXMgYSBsaW5lYXIgdGltZSBjb21wbGV4aXR5IE8obikgYXMgb3Bwb3NlZCB0byBoaWVyYXJjaGljYWwgd2hpY2ggaGFzIGEgcXVhZHJhdGljIGNvbXBsZXhpdHkgLSBPKG5eMikhDQoNCiMjIy0tLSBEZWFsaW5nIHdpdGggb3V0bGllcnMtLS0tLS0tLS0tDQoNCkFsdGhvdWdoIGstbWVhbnMgaXMgc2Vuc2l0aXZlIHRvIG91dGxpZXJzLCBpbiBvdXIgY2FzZSwgdGhlc2Ugb3V0bGllcnMgZ2l2ZSB1c2VmdWwgaW5mb3JtYXRpb24gYWJvdXQgb3VyIGN1c3RvbWVycy4gVGhlcmVmb3JlLCB3ZSB3aWxsIG5vdCByZW1vdmUgdGhlbSBmcm9tIGNvbnNpZGVyYXRpb24hDQoNCg0KIy0tLS0tLS0tLS0tLS0tLS1PUFRJTUFMIE5VTUJFUiBPRiBDTFVTVEVSUy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tDQoNCiNrLW1lYW5zIHJlcXVpcmVzIHVzIHRvIGdpdmUgdGhlIG51bWJlciBvZiBjbHVzdGVycyByZXF1aXJlZCEgDQojVG8gZ2V0IHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycyAtLSB3ZSBjYW4gZG8gYSBudW1iZXIgb2YgdGhpbmdzIC0tLQ0KIzEuIEVsYm93IG1ldGhvZA0KIzIuIFNpbGhvdWV0dGUgbWV0aG9kDQojMy4gR2FwIC0gU3RhdGlzdGljIG1ldGhvZA0KDQojR29hbCBpcyB0byBncm91cCBjdXN0b21lcnMgaW50byBoaWdoIHZhbHVlIGFuZCBsb3cgdmFsdWUgY3VzdG9tZXJzIQ0KDQoNCmBgYHtyfQ0KDQpwcmVfcHJvY2Vzc2VkIDwtIGN1c3RvbWVyc1ssOToxMV0NCg0KZnZpel9uYmNsdXN0KHByZV9wcm9jZXNzZWQsIGttZWFucyxtZXRob2QgPSAid3NzIikNCg0KYGBgDQojVGhlcmVmb3JlLCB0aGUgZWxib3cgbWV0aG9kIHNob3dzIDQgYXMgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzDQoNCmBgYHtyfQ0KDQpmdml6X25iY2x1c3QocHJlX3Byb2Nlc3NlZCwga21lYW5zLG1ldGhvZCA9ICJzaWxob3VldHRlIikNCg0KI1RoZSBTaWxob3VldHRlIG1ldGhvZCBnaXZlcyAzIGFzIHRoZSBvcHRpbWFsIG51bWJlciBvZiBjbHVzdGVycyENCg0KYGBgDQoNCg0KDQpgYGB7cn0NCiNmdml6X25iY2x1c3QocHJlX3Byb2Nlc3NlZCwga21lYW5zLG1ldGhvZCA9ICJnYXBfc3RhdCIpDQoNCiNHYXAgc3RhdGlzdGljIGFsc28gZ2l2ZXMgMyBhcyB0aGUgb3B0aW1hbCBudW1iZXIgb2YgY2x1c3RlcnMhDQoNCmBgYA0KDQoNCiNMZXRzIHRyeSB0byB2aXN1YWxpemUgcmVzdWx0cyBmb3IgY2x1c3RlcnMgMiB0byAxMCBhbmQgY29tcGFyZSByZXN1bHRzIQ0KDQpgYGB7cn0NCg0KbW9kZWxzIDwtIGRhdGEuZnJhbWUoaz1pbnRlZ2VyKCksDQogICAgICAgICAgICAgICAgICAgICB0b3Qud2l0aGluc3M9bnVtZXJpYygpLA0KICAgICAgICAgICAgICAgICAgICAgYmV0d2VlbnNzPW51bWVyaWMoKSwNCiAgICAgICAgICAgICAgICAgICAgIHRvdHNzPW51bWVyaWMoKSwNCiAgICAgICAgICAgICAgICAgICAgIHJzcXVhcmVkPW51bWVyaWMoKSkNCg0KDQpmb3IgKGsgaW4gMToxMCl7DQogIA0KICBvdXRwdXQgPC0ga21lYW5zKHByZV9wcm9jZXNzZWQsIGNlbnRlcnMgPSBrLG5zdGFydCA9IDIwKQ0KICANCiAgdmFyaWFibGVfbmFtZSA8LSBwYXN0ZSgiQ2x1c3RlciIsayxzZXAgPSAiXyIpDQogIA0KICBjdXN0b21lcnNbLCh2YXJpYWJsZV9uYW1lKV0gPC0gb3V0cHV0JGNsdXN0ZXINCiAgDQogIGN1c3RvbWVyc1ssKHZhcmlhYmxlX25hbWUpXSA8LSBmYWN0b3IoY3VzdG9tZXJzWywodmFyaWFibGVfbmFtZSldLCBsZXZlbHMgPSBjKDE6aykpDQogIA0KICANCiAgDQogICNHcmFwaGluZyB0aGUgY2x1c3RlcnMNCiAgY29sb3JzIDwtIGMoJ3JlZCcsJ29yYW5nZScsJ2dyZWVuMycsJ2RlZXBza3libHVlJywnYmx1ZScsJ2RhcmtvcmNoaWQ0JywndmlvbGV0JywncGluazEnLCd0YW4zJywnYmxhY2snKQ0KICB0aXRsZSA8LSBwYXN0ZSgiQ2x1c3RlciBhbmFseXNpcyB3aXRoIixrLCJDbHVzdGVycyIpDQogIA0KICBwNCA8LSBnZ3Bsb3QoZGF0YSA9IGN1c3RvbWVycyxhZXMoeCA9IGxvZ19mcmVxdWVuY3ksIHkgPSBsb2dfcmV2ZW51ZSkpICsNCiAgICBnZW9tX3BvaW50KGFlcyhjb2xvciA9IGN1c3RvbWVyc1ssKHZhcmlhYmxlX25hbWUpXSkpICsgbGFicyhjb2xvciA9ICJDbHVzdGVyIGdyb3VwIikgKyBnZ3RpdGxlKHRpdGxlKQ0KICANCiAgcHJpbnQoZ2dwbG90bHkocDQpKQ0KICANCiAgI0NsdXN0ZXIgY2VudHJlcyBpbiBvcmlnaW5hbCBtZXRyaWNzDQogIA0KICBjbHVzdGVyX2NlbnRyZXMgPC0gZGRwbHkoY3VzdG9tZXJzLC4oY3VzdG9tZXJzWywodmFyaWFibGVfbmFtZSldKSwgc3VtbWFyaXplLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV2ZW51ZSA9IHJvdW5kKG1lZGlhbihyZXZlbnVlKSwyKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlY2VuY3kgPSByb3VuZChtZWRpYW4ocmVjZW5jeSksMiksDQogICAgICAgICAgICAgICAgICAgICAgICAgICBmcmVxdWVuY3kgPSByb3VuZChtZWRpYW4oRnJlcXVlbmN5KSwyKQ0KICApDQogIA0KICBuYW1lcyhjbHVzdGVyX2NlbnRyZXMpW25hbWVzKGNsdXN0ZXJfY2VudHJlcykgPT0gImN1c3RvbWVyc1ssICh2YXJpYWJsZV9uYW1lKV0iXSA8LSAiQ2x1c3RlcnMiDQogIA0KICBwcmludChjbHVzdGVyX2NlbnRyZXMpDQogIGNhdCgiXG4iKQ0KICBjYXQoIlxuIikNCiAgI01vZGVsIEluZm9ybWF0aW9uDQogIA0KICBtb2RlbHNbaywiayJdIDwtIGsNCiAgbW9kZWxzW2ssInRvdC53aXRoaW5zcyJdIDwtIG91dHB1dCR0b3Qud2l0aGluc3MNCiAgbW9kZWxzW2ssImJldHdlZW5zcyJdIDwtIG91dHB1dCRiZXR3ZWVuc3MNCiAgbW9kZWxzW2ssInRvdHNzIl0gPC0gb3V0cHV0JHRvdHNzDQogIG1vZGVsc1trLCJyc3F1YXJlZCJdIDwtIG91dHB1dCRiZXR3ZWVuc3Mvb3V0cHV0JHRvdHNzDQogIA0KfQ0KDQpgYGANCg0KRmluYWwgU29sdXRpb24NCg0KYGBge3J9DQpzY2F0dGVyM2QoeCA9IGN1c3RvbWVycyRsb2dfcmV2ZW51ZSwgeSA9IGN1c3RvbWVycyRsb2dfZnJlcXVlbmN5LCB6ID0gY3VzdG9tZXJzJGxvZ19yZWNlbmN5LA0KICAgICAgICAgIGdyb3VwcyA9IGN1c3RvbWVycyRDbHVzdGVyXzQsDQogICAgICAgICAgeGxhYiA9ICJGcmVxdWVuY3kgKExvZy10cmFuc2Zvcm1lZCkiLA0KICAgICAgICAgIHlsYWIgPSAiTW9uZXRhcnkgVmFsdWUgKGxvZy10cmFuc2Zvcm1lZCkiLA0KICAgICAgICAgIHpsYWIgPSAiUmVjZW5jeSAoTG9nLXRyYW5zZm9ybWVkKSIsDQogICAgICAgICAgc3VyZmFjZS5jb2wgPSBjb2xvcnMsDQogICAgICAgICAgYXhpcy5zY2FsZXMgPSBGQUxTRSwNCiAgICAgICAgICBzdXJmYWNlID0gRkFMU0UsICMgcHJvZHVjZXMgdGhlIGhvcml6b25hbCBwbGFuZXMgdGhyb3VnaCB0aGUgZ3JhcGggYXQgZWFjaCBsZXZlbCBvZiBtb25ldGFyeSB2YWx1ZQ0KICAgICAgICAgIGZpdCA9ICJzbW9vdGgiLA0KICAgICAgICAgIGVsbGlwc29pZCA9IFRSVUUsICMgdG8gZ3JhcGggZWxsaXBzZXMgdXNlcyB0aGlzIGNvbW1hbmQgYW5kIGNvbW1lbnQgb3V0ICJzdXJmYWNlID0gVFJVRSINCiAgICAgICAgICBncmlkID0gRkFMU0UsDQogICAgICAgICAgYXhpcy5jb2wgPSBjKCJibGFjayIsICJibGFjayIsICJibGFjayIpKQ0KDQoNCmBgYA0KDQoNCiMtLS0tLS0tLS0tLUZpbmFsIEFuYWx5c2lzLS0tLS0tLS0tLS0tLS0tLS0tDQoNCiNBcyB0aGUgbnVtYmVyIG9mIGNsdXN0ZXJzIGluY3JlYXNlLCB0aGVyZSBpbnRlcnByZXRhYmlsaXR5IGlzIGFsc28gYWZmZWN0ZWQuDQoNCiNDbHVzdGVyIGFuYWx5c2lzIHdpdGggMiBjbHVzdGVycyBzZWVtcyBvdmVybHkgc2ltcGxpZmllZCENCg0KI0NsdXN0ZXIgYW5hbHlzaXMgd2l0aCAzIGNsdXN0ZXJzIGJhc2ljYWxseSBnaXZlcyBjbHVzdGVyIDMgYXMgaGlnaCB2YWx1ZSBjdXN0b21lcnMsIGNsdXN0ZXIgMSBhbmQgMiBhcmUgc2ltaWxhciAobG93IHZhbHVlISkNCg0KI1RoZSBkZWNpc2lvbiBzaG91bGQgYmUgYmFzZWQgdXBvbiBob3cgdGhlIGJ1c2luZXNzIHBsYW5zIHRvIHVzZSB0aGUgcmVzdWx0cywgYW5kIHRoZSBsZXZlbCBvZiBncmFudWxhcml0eSB0aGV5IHdhbnQgdG8gc2VlIGluIHRoZSBjbHVzdGVycy4gSSdkIHN1Z2dlc3QgNCBudW1iZXIgb2YgY2x1c3RlcnMgc2hvdWxkIGJlIGdvb2QgLS0tIENsdXN0ZXIgNCAtLSBoaWdoIHZhbHVlIGN1c3RvbWVyczsgQ2x1c3RlciAxIGFuZCBDbHVzdGVyIDIgLS0gbWlkIHZhbHVlIGN1c3RvbWVycyBhbmQgQ2x1c3RlciAzIGFyZSB0aGUgemVybyB2YWx1ZSBjdXN0b21lcnMgd2l0aCBsb3cgZnJlcXVlbmN5IGFuZCBsb3cgcmV2ZW51ZSBhbmQgYXJlIG5vdCB2ZXJ5IHJlY2VudC4NCg==